package DFS;

/**
 * 检测图中是否有环
 */
public class CycleDetection {
    private Graph graph;
    private boolean[] visited;
    private boolean hasCycle = false;

    public CycleDetection(Graph graph) {
        this.graph = graph;
        this.visited = new boolean[graph.getVertexNum()];

        for (int v = 0; v < graph.getVertexNum(); v++) {
            if (!this.visited[v]) {
                if (dfs(v, v)) {
                    this.hasCycle = true;
                    break;
                }
            }
        }
    }

    private boolean dfs(int v, int parent) {
        this.visited[v] = true;
        for (int w : graph.adj(v)) {
            if (!this.visited[w]) {
                if (dfs(w, v)) {
                    return true;
                }
            } else if (w != parent) {
                return true;
            }
        }
        return false;
    }

    public boolean hasCycle() {
        return this.hasCycle;
    }


    public static void main(String[] args) {
        Graph graph = new Graph("gNoCycle.txt");
        CycleDetection cd = new CycleDetection(graph);
        System.out.println(cd.hasCycle());
    }
}
